package heap.demo;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:Bite
 * User: 86187
 * Date: 2022-08-08
 * Time: 11:11
 */

public class TestHeap {
    public int[] elem;
    public int usedSize;//当前堆中的有效数据的个数
    public static final int DEFAULT_CAPACITY = 10;


    public TestHeap() {
        this.elem = new int[DEFAULT_CAPACITY];
        this.usedSize = 0;
    }

    public void initArray(int[] array) {
        //初始化数组
        elem = Arrays.copyOf(array,array.length);
        usedSize = array.length;
    }

    /**
     * 建树：大根堆 建树 向下调整
     * 1.如何确定最后一颗子树的最后一个孩子节点的位置？-》len-1
     * 2.确定该孩子节点为【i】，如何确定父亲节点？-》（i-1）/ 2
     *    即最后一颗子树的根节点为 (len-1-1)/2
     * 3.所以只需主要去写每棵子树的调整即可。
     */
    public void createHeap() {
        for (int parent = (usedSize-2)>>>1; parent >= 0; parent--) {
            shiftDown(parent,usedSize);
        }
    }

    /**
     * 实现向下调整！ 时间复杂度: T(n) = n - log(n+1)  约等于 O(n)
     * @param parent 每棵子树根节点的下标
     * @param len 每棵子树的结束位置
     */
    private void shiftDown(int parent,int len) {
        int child = (parent << 1) + 1;
        //最起码要有左孩子
        while(child < len) {
            //判断左 右孩子谁最大,前提是要有右孩子
            if(child+1 < len && elem[child] < elem[child+1]) {
                child++; //保存了最大值的下标
            }
            if(elem[child] > elem[parent]) {
                swap(elem,child,parent);

                parent = child;
                child = (parent << 1) + 1;
            }else {
                break;
            }
        }
    }
    private void swap(int[] array, int begin, int end) {
        int tmp = array[begin];
        array[begin] = array[end];
        array[end] = tmp;
    }

    /**
     *优先级队列 的 插入 ： 向上调整
     */
    public void offer(int x) {
        if(isFull()) {
            int oldCapacity = elem.length;
            int newCapacity = oldCapacity + ((oldCapacity < 64) ? oldCapacity : (oldCapacity >>> 1));
            elem = Arrays.copyOf(elem,newCapacity);//扩容
        }
        this.elem[usedSize++] = x;
        shiftUp(usedSize - 1);
    }
    private void shiftUp(int child) {  //向上调整的实现
        int parent = ((child - 1) >>> 1);
        while(child > 0) {
            if(elem[child] > elem[parent]) {
                swap(elem,child,parent); //交换值
                child = parent;
                parent = ((child - 1) >>> 1);
            }else {
                break;
            }
        }
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 优先级队列 的 删除：删除的是 堆顶的元素
     * 如何删除呢？？
     * 将0下标(堆顶)的数据 与 最后一个数据 交换，然后usedSize--(如果是引用类型，还需要置空),
     * 就可以把堆顶元素删掉，并且这样只有根节点下标为0的这棵树不满足大根堆，只需向下调整这颗树
     */
    public int poll() {
        if(isEmpty()) { return -1; }
        int oldNum = elem[0];

        swap(elem,0,usedSize - 1);
        elem[--usedSize] = 0;

        shiftDown(0,usedSize);

        return oldNum;
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }

    /**
     * 堆排序:升序，从小到大, 建立大根堆
     */
    public void heapSort() {
        //int newUsedSize = usedSize;
        int end = usedSize - 1;
        while(end > 0) {
            swap(elem, 0, end);
            shiftDown(0, end);
            end--;
        }
    }
}
